package com.rr.middle;

/**
 * @author zhuangcanrun
 * @Date 2022/08/10/19:14
 * @description
 **/

/*
* https://leetcode.cn/problems/minimum-path-sum/
* 数组题，找最短路径   用动态规划
* */
public class MinPathSum {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        for (int i = 1; i < row; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < column; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < column; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[row - 1][column - 1];
    }
}


//dfs+枝剪  哒咩
//public class MinPathSum {
//    private int ans,row, column;
//    private int[][] grid;
//
//    public int minPathSum(int[][] grid) {
//        ans = Integer.MAX_VALUE;
//        this.row = grid.length;
//        this.column = grid[0].length;
//        this.grid = grid;
//        getAns(0,0,0);
//        return ans;
//    }
//
//    private void getAns(int total, int currentRow, int currentColumn) {
//        total += grid[currentRow][currentColumn];
//        if (total > ans) {
//            return;
//        }
//        if (currentRow == row - 1 && currentColumn == column - 1) {
//            ans = Math.min(total, ans);
//        }
//        if (currentRow < row - 1) {
//            getAns(total, currentRow + 1, currentColumn);
//        }
//        if (currentColumn < column - 1) {
//            getAns(total, currentRow, currentColumn + 1);
//        }
//    }
//}
